/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.ComponentModel;
using Xceed.Silverlight.Data.Stats;

namespace Xceed.Silverlight.Data
{
  internal class CacheEnumerator<T> : AsyncParentEnumerator<T>
  {
    #region Static Fields

    private static readonly Guid JumpMoveAndFetchCallId = DataUtils.CreateCallId();
    private static readonly Guid GetStatValuesCallId = DataUtils.CreateCallId();

    #endregion Static Fields


    internal CacheEnumerator(
      int cacheSize,
      IDataHelper dataHelper,
      IAsyncEnumerator<T> child )
      : base( child )
    {
      if( cacheSize < 0 )
        throw new ArgumentOutOfRangeException( "cacheSize", "cacheSize must be greater than or equal to zero." );

      m_dataHelper = dataHelper;
      m_cacheSize = cacheSize;
    }


    #region DataHelper Property

    internal IDataHelper DataHelper
    {
      get
      {
        return m_dataHelper;
      }
    }

    #endregion DataHelper Property

    #region CacheSize Property

    internal int CacheSize
    {
      get
      {
        return m_cacheSize;
      }
    }

    #endregion CacheSize Property

    #region CachedItems Property

    internal List<T> CachedItems
    {
      get
      {
        return m_cachedItems;
      }
    }

    #endregion CachedItems Property

    #region TotalItemCount Property

    internal EstimateInt64 TotalItemCount
    {
      get
      {
        return m_totalItemCount;
      }
      set
      {
        m_totalItemCount = value;
      }
    }

    private EstimateInt64 m_totalItemCount; //null

    #endregion TotalItemCount Property


    #region CachedStatResults

    internal IDictionary<StatParameters, StatResults> CachedStatResults
    {
      get
      {
        return m_cachedStatResults;
      }
    }

    #endregion CachedStatResults


    #region ReferencePosition Property

    internal RelativeOffset FirstItemOffset
    {
      get
      {
        return m_firstItemOffset;
      }
    }

    #endregion ReferencePosition Property

    #region IsCacheAtStart Property

    protected bool IsCacheAtStart
    {
      get
      {
        return ( this.CalculateCacheLimitPosition( true ) == CachePositionState.Yes );
      }
    }

    #endregion IsCacheAtStart Property

    #region IsCacheAtEnd Property

    protected bool IsCacheAtEnd
    {
      get
      {
        return ( this.CalculateCacheLimitPosition( false ) == CachePositionState.Yes );
      }
    }

    #endregion IsCacheAtEnd Property

    #region IsCacheComplete Property

    private bool IsCacheComplete
    {
      get
      {
        return this.IsCacheAtStart && this.IsCacheAtEnd;
      }
    }

    #endregion IsCacheComplete Property


    internal int CachedItemsCount
    {
      get
      {
        return m_cachedItems.Count;
      }
    }

    private CachePositionState CalculateCacheLimitPosition( bool atStartPosition )
    {
      return this.CalculateCacheLimitPosition(
        atStartPosition,
        m_cachedItems.Count,
        m_firstItemOffset,
        m_totalItemCount );
    }

    private CachePositionState CalculateCacheLimitPosition(
      bool atStartPosition,
      int cacheCount,
      RelativeOffset offset,
      EstimateInt64 totalCount )
    {
      EstimateInt64 limitOffset = this.CalculateLimitOffset(
          atStartPosition,
          offset,
          totalCount );

      CachePositionState state = CachePositionState.Maybe;

      if( limitOffset != null && !limitOffset.IsEstimate )
      {
        if( atStartPosition )
        {
          state = ( limitOffset.Value <= 1 )
            ? CachePositionState.Yes
            : CachePositionState.No;
        }
        else
        {
          state = ( limitOffset.Value <= cacheCount )
            ? CachePositionState.Yes
            : CachePositionState.No;
        }
      }

      return state;
    }


    private EstimateInt64 CalculateLimitOffset(
      bool beforeFirstOffset,
      RelativeOffset providedOffset,
      EstimateInt64 totalCount )
    {
      EstimateInt64 offset = null;
      if( providedOffset != null )
      {
        if( ( ( providedOffset.ReferencePosition == ReferencePoint.BeforeFirst ) && beforeFirstOffset )
          || ( ( providedOffset.ReferencePosition != ReferencePoint.BeforeFirst ) && !beforeFirstOffset ) )
        {
          offset = providedOffset.EstimateValue;
        }
        else if( totalCount != null )
        {
          offset = ( totalCount - providedOffset.EstimateValue ) + 1;
        }
      }
      return offset;
    }

    internal void UpdateCountInformation( RelativeOffset firstItemOffset )
    {
      this.UpdateCountInformation( firstItemOffset, m_totalItemCount );
    }

    internal void UpdateCountInformation( EstimateInt64 totalCount )
    {
      this.UpdateCountInformation( m_firstItemOffset, totalCount );
    }

    internal void UpdateCountInformation( RelativeOffset firstItemOffset, EstimateInt64 totalCount )
    {

      if( ( firstItemOffset != null && m_firstItemOffset != null )
        && ( firstItemOffset.ReferencePosition != m_firstItemOffset.ReferencePosition ) )
      {

        if( totalCount == null
          || ( totalCount.IsEstimate && !firstItemOffset.IsEstimate && !m_firstItemOffset.IsEstimate ) )
        {
          totalCount = firstItemOffset.EstimateValue + m_firstItemOffset.EstimateValue;
          totalCount -= 1;
        }
      }

      bool isRealReference = ( firstItemOffset != null ) && ( !firstItemOffset.IsEstimate );
      bool isRealTotal = ( totalCount != null ) && ( !totalCount.IsEstimate );

      if( isRealTotal )
      {
        m_totalItemCount = totalCount;
      }

      if( isRealReference )
      {
        m_firstItemOffset = firstItemOffset;
      }

      if( isRealReference )
      {
        EstimateInt64 otherReference =
          ( m_totalItemCount != null && !m_totalItemCount.IsEstimate )
          ? m_totalItemCount.Value - m_firstItemOffset.Value + 1
          : ( EstimateInt64 )null;

        EstimateInt64 beforeFirstReference =
          ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst )
          ? m_firstItemOffset.EstimateValue
          : otherReference;

        EstimateInt64 afterLastReference =
          ( m_firstItemOffset.ReferencePosition == ReferencePoint.AfterLast )
          ? m_firstItemOffset.EstimateValue
          : otherReference;

        if( beforeFirstReference != null && beforeFirstReference.Value <= 0 )
        {
          int removeItemCount = Convert.ToInt32( -beforeFirstReference.Value + 1 );


          m_cachedItems.RemoveRange( 0, removeItemCount );

          m_firstItemOffset = DataUtils.CalculateRelativeOffset( m_firstItemOffset, removeItemCount );

          firstItemOffset = DataUtils.CalculateRelativeOffset( firstItemOffset, removeItemCount );
        }

        if( afterLastReference != null && ( afterLastReference.Value < m_cachedItems.Count ) )
        {
          int removeItemCount = Convert.ToInt32( m_cachedItems.Count - afterLastReference.Value );



          m_cachedItems.RemoveRange(
            Convert.ToInt32( m_cachedItems.Count - removeItemCount ),
            removeItemCount );
        }
      }

      if( isRealTotal && m_totalItemCount.Value < m_cachedItems.Count )
      {
        Debug.Assert( m_firstItemOffset == null || m_firstItemOffset.IsEstimate,
          "This should have been handled in the previous if" );
        Debug.Assert( false );
      }

      if( firstItemOffset != null )
      {
        if( ( ( firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst ) && firstItemOffset.Value <= 0 )
          || ( ( firstItemOffset.ReferencePosition == ReferencePoint.AfterLast ) && firstItemOffset.Value < m_cachedItems.Count ) )
        {
          Debug.Assert( firstItemOffset.IsEstimate );
          firstItemOffset = m_firstItemOffset;
        }
      }

      if( totalCount != null && totalCount.Value < m_cachedItems.Count )
      {
        Debug.Assert( totalCount.IsEstimate );
        totalCount = m_totalItemCount;
      }

      bool isCacheAtStart = this.IsCacheAtStart;
      bool isCacheAtEnd = this.IsCacheAtEnd;

      bool newCacheAtStart = this.CalculateCacheLimitPosition(
        true,
        m_cachedItems.Count,
        firstItemOffset,
        totalCount ) == CachePositionState.Yes;

      bool newCacheAtEnd = this.CalculateCacheLimitPosition(
        false,
        m_cachedItems.Count,
        firstItemOffset,
        totalCount ) == CachePositionState.Yes;

      if( isCacheAtStart && !newCacheAtStart )
      {
        firstItemOffset = null;
        if( m_firstItemOffset.ReferencePosition == ReferencePoint.AfterLast )
        {
          totalCount = null;
        }
      }

      if( isCacheAtEnd && !newCacheAtEnd )
      {
        firstItemOffset = null;
        if( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst )
        {
          totalCount = null;
        }
      }

      if( firstItemOffset != null )
      {
        m_firstItemOffset = firstItemOffset;
      }

      if( totalCount != null )
      {
        m_totalItemCount = totalCount;
      }
    }

    internal void SetCacheSize( int size, double topTrimRatio )
    {
      if( topTrimRatio < 0 || topTrimRatio > 1 )
        throw new ArgumentOutOfRangeException( "topTrimRatio", "topTrimRation must be greater than or equal to zero and less than or equal to one." );

      int removeCount = Math.Max( 0, m_cachedItems.Count - this.CacheSize );
      int removeFromStart = ( int )( removeCount * topTrimRatio );

      this.SetCacheSize( size, removeFromStart );
    }

    internal void SetCacheSize( int size, SourcePosition topLimitTrim )
    {
      Nullable<int> topLimitIndex = null;

      if( topLimitTrim != null )
      {
        topLimitIndex = this.FindSourcePositionIndex( topLimitTrim, 0, 1 );
      }

      this.SetCacheSize( size, topLimitIndex.GetValueOrDefault( 0 ) );
    }

    private void SetCacheSize( int size, int topLimitTrim )
    {
      if( size < 0 )
        throw new ArgumentOutOfRangeException( "size", "size must be greater than or equal to zero." );

      if( m_cacheSize != size )
      {
        if( m_cacheSize < size )
        {
          m_cacheSize = size;
        }
        else
        {
          m_cacheSize = size;
          this.TrimCache( topLimitTrim );
        }
      }
    }

    #region Begin/End GetStatValues

    public override IAsyncResult BeginGetStatValues( StatParameters parameters, AsyncCallback userCallback, object asyncState )
    {
      ContextAsyncResult asyncResult = new ContextAsyncResult( CacheEnumerator<T>.GetStatValuesCallId, userCallback, asyncState );
      asyncResult.CallContext = parameters;

      StatResults results;

      if( m_cachedStatResults.TryGetValue( parameters, out results ) )
      {
        asyncResult.StartSync( results );
      }
      else
      {
        asyncResult.Start(
          ( callback, state ) => base.BeginGetStatValues( parameters, callback, state ),
            ( parentAr, childAr ) => new DependentCallResult( base.EndGetStatValues( childAr ) ) );
      }
      return asyncResult;
    }

    public override StatResults EndGetStatValues( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( CacheEnumerator<T>.GetStatValuesCallId );
      StatResults results = asyncResult.GetCallResult<StatResults>();
      StatParameters parameters = ( StatParameters )( ( ContextAsyncResult )asyncResult ).CallContext;

      if( !m_cachedStatResults.ContainsKey( parameters ) )
      {
        m_cachedStatResults.Add( parameters, results );
      }

      return results;
    }

    #endregion Begin/End GetStatValues



    #region Begin/End JumpMoveAndFetch

    public override JumpMoveAndFetchAsyncResult BeginJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback userCallback,
      object asyncState )
    {
      this.CheckMoveAndFetchParameters(
        parameters.ExpectedMoveCount,
        parameters.ExpectedFetchCount );

      CacheJumpAsyncResult cacheAsyncResult = new CacheJumpAsyncResult(
                                               CacheEnumerator<T>.JumpMoveAndFetchCallId,
                                               userCallback,
                                               asyncState,
                                               parameters );

      long actualMove;
      IList<T> cacheData;
      SourcePosition endPosition;
      bool operationCompleted;
      Nullable<int> sourcePositionIndex;
      RelativeOffset endPositionOffset;
      EstimateInt64 totalCount;


      this.UpdateCountInformation( m_firstItemOffset.ToEstimate(), m_totalItemCount.ToEstimate() );

      bool result = this.CacheJumpMoveAndFetch(
                      parameters,
                      out actualMove,
                      out cacheData,
                      out endPosition,
                      out sourcePositionIndex,
                      out operationCompleted,
                      out endPositionOffset,
                      out totalCount );

      if( operationCompleted )
      {
        Debug.Assert( endPosition != null );

        cacheAsyncResult.StartSync(
          new JumpMoveAndFetchResult<T>(
            cacheAsyncResult,
            actualMove,
            cacheData,
            result,
            endPosition,
            endPositionOffset,
            totalCount ) );
      }
      else
      {
        Debug.Assert( cacheData == null || cacheData.Count != 0 );

        long childMove = parameters.ExpectedMoveCount;
        int childFetch = parameters.ExpectedFetchCount;
        bool childApproximateMove = parameters.ApproximateMove;
        SourcePosition childFetchStart = parameters.SourcePosition;

        if( cacheData != null )
        {
          Debug.Assert( actualMove == parameters.ExpectedMoveCount );

          int fetchUnit = DataUtils.GetUnit( cacheAsyncResult.ExpectedFetchCount );

          childMove = fetchUnit;
          childFetch -= ( cacheData.Count * fetchUnit );
          childFetchStart = endPosition;
        }
        else if( actualMove != 0 )
        {
          Debug.Assert( m_cachedItems.Count != 0 );

          childMove -= actualMove;
          childFetchStart = endPosition;
        }

        cacheAsyncResult.CacheData = cacheData;
        cacheAsyncResult.CacheMove = actualMove;
        cacheAsyncResult.CacheEndPositionOffset = endPositionOffset;
        cacheAsyncResult.CacheTotalCount = totalCount;

        cacheAsyncResult.Start(
          ( callback, state ) => this.BeginChildJumpMoveAndFetch(
                                   new JumpMoveAndFetchParameters(
                                     childFetchStart,
                                     childMove,
                                     childFetch,
                                     childApproximateMove ),
                                   callback,
                                   state ),
          null );

        return cacheAsyncResult;
      }

      return cacheAsyncResult;
    }

    protected virtual JumpMoveAndFetchAsyncResult BeginChildJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback userCallback,
      object asyncState )
    {
      return this.ChildEnumeratorTyped.BeginJumpMoveAndFetch(
        parameters,
        userCallback,
        asyncState );
    }

    private JumpMoveAndFetchResult<T> CombineResults( CacheJumpAsyncResult cacheAsyncResult, JumpMoveAndFetchResult<T> childResult )
    {
      Debug.Assert( childResult.GetFetchUnit() == cacheAsyncResult.GetFetchUnit() );

      List<T> fetchedData = cacheAsyncResult.CacheData as List<T>;
      Nullable<long> actualMove = null;
      ICollection<T> fetchedItems = null;

      if( fetchedData == null && cacheAsyncResult.CacheData != null )
      {
        fetchedData = new List<T>( cacheAsyncResult.CacheData );
      }

      Debug.Assert( ( ( fetchedData != null ) && childResult.ExpectedMoveCount == cacheAsyncResult.GetFetchUnit() )
        || ( ( fetchedData == null ) && childResult.GetMoveUnit() == cacheAsyncResult.GetMoveUnit() ) );

      if( cacheAsyncResult.CacheMove != cacheAsyncResult.ExpectedMoveCount )
      {
        if( childResult.ActualMoveCount.HasValue )
        {
          actualMove = cacheAsyncResult.CacheMove + childResult.ActualMoveCount.Value;
        }
      }
      else
      {
        actualMove = cacheAsyncResult.CacheMove;
      }

      if( fetchedData != null )
      {
        if( childResult.FetchedItems != null )
        {
          fetchedData.AddRange( childResult.FetchedItems );
        }

        fetchedItems = fetchedData;
      }
      else
      {
        fetchedItems = childResult.FetchedItems;
      }

      RelativeOffset endPositionOffset = null;
      EstimateInt64 totalCount = null;

      if( childResult.EndPositionOffset == null )
      {
        Debug.Assert( childResult.ActualMoveCount.HasValue, "Child should return a reference position if the move failed" );

        long offset = childResult.GetFetchDisplacement();

        offset += ( cacheAsyncResult.CacheMove != childResult.ActualMoveCount.Value )
          ? childResult.ActualMoveCount.Value
          : childResult.GetFetchUnit();

        endPositionOffset = DataUtils.CalculateRelativeOffset( cacheAsyncResult.CacheEndPositionOffset, offset );
      }
      else
      {
        endPositionOffset = childResult.EndPositionOffset;
      }

      if( childResult.TotalCount != null )
      {
        totalCount = childResult.TotalCount;
      }
      else
      {
        totalCount = cacheAsyncResult.CacheTotalCount;
      }

      return
        new JumpMoveAndFetchResult<T>(
        cacheAsyncResult,
        actualMove,
        fetchedItems,
        childResult.Result,
        childResult.EndPositionObject,
        endPositionOffset,
        totalCount );
    }

    public override JumpMoveAndFetchResult<T> EndJumpMoveAndFetch( JumpMoveAndFetchAsyncResult jumpMoveAndFetchAsyncResult )
    {
      if( m_disposed )
        return null;

      jumpMoveAndFetchAsyncResult.ValidateCallEnd( CacheEnumerator<T>.JumpMoveAndFetchCallId );

      CacheJumpAsyncResult cacheAsyncResult = ( CacheJumpAsyncResult )jumpMoveAndFetchAsyncResult;

      JumpMoveAndFetchResult<T> cacheOnlyOperationResult = cacheAsyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();

      //It will be started synchronously if all data was extracted from the cache.
      //No need to merge it.
      if( cacheOnlyOperationResult != null )
        return cacheOnlyOperationResult;

      JumpMoveAndFetchResult<T> childResult = this.ChildEnumeratorTyped.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )cacheAsyncResult.LastIAsyncResult );

      this.MergeResult( childResult );

      if( childResult.FetchedItems != null && childResult.FetchedItems.Count != 0 )
      {
        int topLimitIndex =
          jumpMoveAndFetchAsyncResult.IsFetchingForward()
          ? m_cachedItems.Count - 1
          : 0;

        this.TrimCache( topLimitIndex );
      }

      return this.CombineResults( cacheAsyncResult, childResult );
    }

    #endregion Begin/End JumpMoveAndFetch

    protected bool CacheJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      out long actualMoveCount,
      out IList<T> fetchedItems,
      out SourcePosition endPosition,
      out Nullable<int> sourcePositionIndex,
      out bool complete,
      out RelativeOffset endPositionOffset,
      out EstimateInt64 totalCount )
    {
      SourcePosition sourcePosition = parameters.SourcePosition;
      long expectedMoveCount = parameters.ExpectedMoveCount;
      int expectedFetchCount = parameters.ExpectedFetchCount;

      bool result;

      sourcePositionIndex = this.FindSourcePositionIndex( sourcePosition, expectedMoveCount, expectedFetchCount );

      if( !sourcePositionIndex.HasValue || ( m_cachedItems.Count == 0 && !this.IsCacheComplete ) )
      {
        actualMoveCount = 0;
        fetchedItems = null;
        endPosition = sourcePosition;
        result = true;
        complete = false;
        endPositionOffset = null;
        totalCount = m_totalItemCount;
      }
      else
      {
        //Get the available data in cache.
        result = this.FetchCacheData(
                   sourcePositionIndex.Value,
                   expectedMoveCount,
                   expectedFetchCount,
                   out actualMoveCount,
                   out fetchedItems,
                   out endPosition,
                   out endPositionOffset,
                   out totalCount );

        if( endPosition == null )
        {
          Debug.Assert( actualMoveCount == 0 );
          Debug.Assert( fetchedItems == null );
          endPosition = sourcePosition;
          complete = false;
        }
        else
        {
          complete = endPosition.IsOutOfBound;
          complete = complete || ( fetchedItems != null ) && ( fetchedItems.Count == Math.Abs( expectedFetchCount ) );
        }
      }

      return result;
    }

    protected virtual void ChildDataRemoved( T oldItem, SourcePosition removePosition )
    {
      Nullable<int> removeIndex = ( this.CachedItemsCount != 0 )
        ? this.GetRemoveIndex( oldItem )
        : ( Nullable<int> )null;

      this.HandleItemChangeCore( true, removeIndex, false, null, default( T ) );
    }

    protected virtual void ChildDataAdded( T newItem )
    {
      Nullable<int> insertIndex = ( this.CachedItemsCount != 0 )
        ? this.GetInsertIndex( newItem )
        : ( Nullable<int> )null;

      this.HandleItemChangeCore( false, null, true, insertIndex, newItem );
    }

    protected virtual void ChildDataReseted()
    {
      m_cachedItems.Clear();
      this.ClearItemCountEstimates();
      m_totalItemCount = m_totalItemCount.ToEstimate();
    }

    protected virtual void ChildDataReplaced( T oldItem, T newItem )
    {
      Nullable<int> removeIndex = null;
      Nullable<int> insertIndex = null;

      if( this.CachedItemsCount != 0 )
      {
        removeIndex = this.GetRemoveIndex( oldItem );
        insertIndex = this.GetInsertIndex( newItem );
      }

      this.HandleItemChangeCore( true, removeIndex, true, insertIndex, newItem );
    }

    protected virtual void ChildDataItemChanged( ItemChangedInfo itemChangedInfo )
    {
      if( itemChangedInfo == null )
        throw new ArgumentNullException( "itemChangedInfo" );

      List<SortDescription> completeSort = m_dataHelper.CompleteSort.ToList();

      if( !completeSort.Any( itemChangedInfo.GetIsValueChanged ) )
      {
        return;
      }

      Nullable<int> removeIndex = null;
      Nullable<int> insertIndex = null;

      T item = ( T )itemChangedInfo.Target;

      if( this.CachedItemsCount != 0 )
      {
        removeIndex = this.GetModifiedItemIndexInfo( completeSort, itemChangedInfo );
        insertIndex = this.GetInsertIndex( item );
      }

      //A property changed on a sorted field is much like a "Replace" of the item with it's old value
      //for the item with the new value.
      this.HandleItemChangeCore( true, removeIndex, true, insertIndex, item );
    }

    protected override void ChildDataChanged( DataChangedEventArgs args )
    {
      if( args.Action == DataChangedAction.Remove )
      {
        this.ChildDataRemoved( ( T )args.OldItem, args.RemovePosition );
      }
      else if( args.Action == DataChangedAction.Add )
      {
        this.ChildDataAdded( ( T )args.NewItem );
      }
      else if( args.Action == DataChangedAction.Reset )
      {
        this.ChildDataReseted();
      }
      else if( args.Action == DataChangedAction.Replace )
      {
        this.ChildDataReplaced( ( T )args.OldItem, ( T )args.NewItem );
      }
      else if( args.Action == DataChangedAction.ItemChanged )
      {
        this.ChildDataItemChanged( args.ItemChangedInfo );
      }
      else
      {
        Debug.Assert( false );
      }

      base.ChildDataChanged( args );
    }

    // If possible, insert the new item in cache, remove the old item,
    // and update the cache's count values appropriatly.
    // 
    // "haveOldItem/haveNewItem" :
    // 
    // "null" indicates that there may be an [old/new] item.
    // true indicates that there is an [old value/new value] that was [removed/added] in the data source
    // false indicates that there is no [old value/new value] at all. No item was [removed/added] in the data source
    // 
    // "oldIndex/newIndex":  
    // 
    // The value is useless if "haveXXXItem" is "false"
    // "null" indicates that we don't know where the item is located in relation to the cache.
    // int.MinValue indicates that the item is before the cache's first item.
    // int.MaxValue indicates that the item is after the cache's last item.
    // Any other int value refers to the actual [remove/insertion] index in the cache. "haveXXXItem" will be forced to true in this case.
    // 
    // newItem is useless if "haveNewItem" is "false" or if newIndex is null.
    internal void HandleItemChangeCore(
      Nullable<bool> haveOldItem, Nullable<int> oldIndex,
      Nullable<bool> haveNewItem, Nullable<int> newIndex, T newItem )
    {
      // Just to be consistent. Clear any useless values
      if( haveOldItem == false )
        oldIndex = null;

      if( haveNewItem == false )
        newIndex = null;

      //If there is a valid remove index, there is an item to remove
      if( oldIndex != null && oldIndex != int.MinValue && oldIndex != int.MaxValue )
      {
        haveOldItem = true;
      }

      //If there is a valid insert index, there is an item to add.
      if( newIndex != null && newIndex != int.MinValue && newIndex != int.MaxValue )
      {
        haveNewItem = true;
      }

      //Add the new item first. 
      //it may keep reference count if the cache is 1 and the removed item is the last one.
      if( newIndex != null && newIndex >= 0 && newIndex <= m_cachedItems.Count )
      {
        m_cachedItems.Insert( newIndex.Value, newItem );

        if( oldIndex != null
          && oldIndex != int.MinValue && oldIndex != int.MaxValue
          && oldIndex >= newIndex )
        {
          oldIndex++;
        }
      }

      //Remove the old item.
      if( oldIndex != null && oldIndex >= 0 && oldIndex < m_cachedItems.Count )
      {
        m_cachedItems.RemoveAt( oldIndex.Value );
      }

      // Update the count information
      RelativeOffset newOffset = null;
      EstimateInt64 newTotalCount = null;

      if( m_cachedItems.Count == 0 )
      {
        this.ClearItemCountEstimates();
      }
      else if( m_firstItemOffset != null )
      {
        if( ( haveOldItem == true && oldIndex == null )
          || ( haveNewItem == true && newIndex == null )
          || ( haveOldItem == null )
          || ( haveNewItem == null ) )
        {
          newOffset = m_firstItemOffset.ToEstimate();
        }
        else
        {
          bool oldIsBeforeFirst = ( haveOldItem.Value ) ? ( oldIndex.Value < 0 ) : false;
          bool newIsBeforeFirst = ( haveNewItem.Value ) ? ( newIndex.Value < 0 ) : false;

          if( haveOldItem.Value && haveNewItem.Value )
          {
            if( oldIsBeforeFirst != newIsBeforeFirst )
            {
              if( oldIsBeforeFirst == ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst ) )
              {
                newOffset = m_firstItemOffset - 1;
              }
            }
          }
          else if( haveOldItem.Value )
          {
            if( oldIsBeforeFirst == ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst ) )
            {
              newOffset = m_firstItemOffset - 1;
            }
          }
          else if( haveNewItem.Value )
          {
            if( newIsBeforeFirst == ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst ) )
            {
              newOffset = m_firstItemOffset + 1;
            }
          }
        }
      }

      if( m_totalItemCount != null )
      {
        if( haveOldItem == null || haveNewItem == null )
        {
          newTotalCount = m_totalItemCount.ToEstimate();
        }
        else if( haveOldItem != haveNewItem )
        {
          newTotalCount = ( haveOldItem.Value )
            ? m_totalItemCount - 1
            : m_totalItemCount + 1;
        }
      }

      this.UpdateCountInformation( newOffset, newTotalCount );
    }

    // Return the index where the item should be inserted.
    //
    // int.MinValue will be returned if the item is placed to an unknown offset before
    // the cache's first item.
    //
    // int.MaxValue will be returned if the item is placed to an unknow offset after
    // the cache's last item.
    //
    // If "equal" items are is already inside the cache, the index will be place
    // after the last "equal" item.
    //
    // Execpt for the "Min/Max" Values, the return value should always be ">= 0" and
    // "<= this.CachedItemsCount".
    internal int GetInsertIndex( T item )
    {
      if( this.CachedItemsCount == 0 )
        throw new DataInternalException();

      int insertIndex = 0;

      while( insertIndex < this.CachedItems.Count )
      {
        if( this.DataHelper.Compare( item, m_cachedItems[ insertIndex ] ) < 0 )
          break;

        insertIndex++;
      }

      // Except when the cache is "at start",
      // an insertIndex of 0, this means that the item 
      // is "somewhere" before the first cache item,
      // not necessarly "right before" the first.
      // That is why I can't insert it in this case.
      // Same concept apply for the last item.

      if( ( insertIndex == 0 ) && ( !this.IsCacheAtStart ) )
      {
        insertIndex = int.MinValue;
      }
      else if( ( insertIndex == m_cachedItems.Count ) && ( !this.IsCacheAtEnd ) )
      {
        insertIndex = int.MaxValue;
      }

      return insertIndex;
    }

    internal int GetRemoveIndex( T item )
    {
      if( this.CachedItemsCount == 0 )
        throw new DataInternalException();

      int index = m_cachedItems.IndexOf( item );

      if( index == -1 )
      {
        index = m_dataHelper.Compare( item, m_cachedItems[ 0 ] ) < 0
          ? int.MinValue
          : int.MaxValue;

        Debug.Assert( index != int.MinValue || !this.IsCacheAtStart );
        Debug.Assert( index != int.MaxValue || !this.IsCacheAtEnd );
      }

      return index;
    }

    internal virtual int GetModifiedItemIndex( T item )
    {
      return m_cachedItems.IndexOf( item );
    }

    internal Nullable<int> GetModifiedItemIndexInfo(
      IList<SortDescription> completeSort,
      ItemChangedInfo itemChangedInfo )
    {
      if( this.CachedItemsCount == 0 )
        throw new DataInternalException();

      Nullable<int> index = this.GetModifiedItemIndex( ( T )itemChangedInfo.Target );

      if( index == -1 )
      {
        //Use the obvious. It's not in cache.
        if( this.IsCacheAtStart )
        {
          index = int.MaxValue;
        }
        else if( this.IsCacheAtEnd )
        {
          index = int.MinValue;
        }
      }

      if( index == -1 )
      {
        Nullable<int> relativeIndex = null;
        T item = ( T )itemChangedInfo.Target;

        foreach( SortDescription sortDescription in completeSort )
        {
          object firstCacheItemValue = m_dataHelper.GetMemberValue( sortDescription.PropertyName, m_cachedItems[ 0 ] );

          int compareResult;

          if( !itemChangedInfo.GetIsValueChanged( sortDescription ) )
          {
            object currentSortValue = m_dataHelper.GetMemberValue( sortDescription.PropertyName, item );
            compareResult = m_dataHelper.CompareValues( currentSortValue, firstCacheItemValue, sortDescription );
          }
          else
          {
            object oldValue;
            if( !itemChangedInfo.TryGetOldValue( sortDescription, out oldValue ) )
              break;

            compareResult = m_dataHelper.CompareValues( oldValue, firstCacheItemValue, sortDescription );
          }


          if( compareResult != 0 )
          {
            relativeIndex = ( compareResult < 0 )
              ? int.MinValue
              : int.MaxValue;
            break;
          }
        }

        Debug.Assert( relativeIndex != null, "Complete equality with complete old values." );

        index = relativeIndex;
      }

      return index;
    }

    protected virtual Nullable<int> FindSourcePositionIndex( SourcePosition sourcePosition, long expectedMoveCount, int expectedFetchCount )
    {
      bool cacheContainFirst = this.IsCacheAtStart;
      bool cacheContainLast = this.IsCacheAtEnd;

      return DataUtils.FindSortedIndexForOperation(
        m_cachedItems,
        cacheContainFirst,
        cacheContainLast,
        expectedMoveCount,
        expectedFetchCount,
        sourcePosition,
        m_dataHelper );
    }

    protected override void Dispose( bool disposing )
    {
      m_disposed = true;

      if( disposing )
      {
        this.FlushCache( 0, false );
      }

      base.Dispose( disposing );
    }

    protected virtual void TrimCache(
      int removeCount,
      int topLimitIndex,
      out int removeFromStart,
      out int removeFromEnd )
    {
      removeFromStart = 0;
      removeFromEnd = 0;

      removeFromStart = Math.Min( topLimitIndex, removeCount );
      removeFromEnd = removeCount - removeFromStart;
    }

    private bool FetchCacheData(
      int startIndex,
      long moveCount,
      int fetchCount,
      out long actualMove,
      out IList<T> data,
      out SourcePosition endPosition,
      out RelativeOffset endPositionOffset,
      out EstimateInt64 totalCount )
    {
      Debug.Assert( m_cachedItems.Count > 0 || this.IsCacheComplete );
      Debug.Assert( startIndex >= -1 && startIndex <= m_cachedItems.Count );

      data = null;
      endPositionOffset = null;
      totalCount = m_totalItemCount;
      endPosition = null;

      bool isCacheAtStart = this.IsCacheAtStart;
      bool isCacheAtEnd = this.IsCacheAtEnd;

      long index = startIndex + moveCount;
      long reachedIndex = index;
      bool ret = true;

      if( isCacheAtEnd && isCacheAtStart )
      {
        totalCount = new EstimateInt64( m_cachedItems.Count, false );
      }

      if( startIndex < 0 && moveCount <= 0 && !isCacheAtStart )
      {
        actualMove = 0;
        endPosition = null;
        return true;
      }

      if( startIndex >= m_cachedItems.Count && moveCount >= 0 && !isCacheAtEnd )
      {
        actualMove = 0;
        endPosition = null;
        return true;
      }

      int lowLimitIndex = ( isCacheAtStart ) ? -1 : 0;
      int upLimitIndex = ( isCacheAtEnd ) ? m_cachedItems.Count : m_cachedItems.Count - 1;

      int endIndex = Convert.ToInt32( Math.Max( lowLimitIndex, Math.Min( upLimitIndex, startIndex + moveCount ) ) );
      actualMove = endIndex - startIndex;

      if( endIndex == -1 )
      {
        Debug.Assert( isCacheAtStart );

        endPosition = SourcePosition.BeforeFirst;
        ret = false;
      }
      else if( endIndex == m_cachedItems.Count )
      {
        Debug.Assert( isCacheAtEnd );

        endPosition = SourcePosition.AfterLast;
        ret = false;
      }

      if( ret )
      {
        if( actualMove == moveCount )
        {
          Debug.Assert( endIndex - startIndex == moveCount );

          if( fetchCount == 0 )
          {
            data = new List<T>();
            endPosition = new ItemPosition( m_cachedItems[ endIndex ] );
          }
          else
          {
            int beginIndex = endIndex;
            int fetchUnit = DataUtils.GetUnit( fetchCount );
            endIndex = Math.Max( 0, Math.Min( m_cachedItems.Count - 1, beginIndex + fetchCount - fetchUnit ) );


            List<T> retData = m_cachedItems.GetRange(
                                Math.Min( endIndex, beginIndex ),
                                Math.Abs( endIndex - beginIndex ) + 1 );

            if( fetchUnit > 0 )
            {
              ret = ( retData.Count == Math.Abs( fetchCount ) || !isCacheAtEnd );
            }
            else
            {
              ret = ( retData.Count == Math.Abs( fetchCount ) || !isCacheAtStart );
              retData.Reverse();
            }

            if( !ret )
            {
              endPosition = ( fetchUnit > 0 )
                ? SourcePosition.AfterLast
                : SourcePosition.BeforeFirst;

              endIndex += fetchUnit;
            }
            else
            {
              endPosition = new ItemPosition( retData[ retData.Count - 1 ] );
            }

            data = retData;
          }
        }
        else
        {
          endPosition = new ItemPosition( m_cachedItems[ endIndex ] );
        }
      }

      endPositionOffset = DataUtils.CalculateRelativeOffset( m_firstItemOffset, endIndex );

      return ret;
    }

    private void MergeResult( JumpMoveAndFetchResult<T> result )
    {
      EstimateInt64 fetchedItemsStartIndex = null;
      RelativeOffset firstItemOffset = null;


      this.ExtractIndexes( result, out fetchedItemsStartIndex, out firstItemOffset );

      if( ( fetchedItemsStartIndex == null || fetchedItemsStartIndex.IsEstimate )
        && ( result.FetchedItems != null && result.FetchedItems.Count > 0 ) )
      {
        //By no means can we merge the actual fetched items into the cache. Just override the cache with 
        //the recently fetched data.
        this.ReplaceCache( result );
        return;
      }

      //Merge count information
      this.UpdateCountInformation( firstItemOffset, result.TotalCount );

      //Merge items
      if( result.FetchedItems != null && result.FetchedItems.Count > 0 )
      {
        Debug.Assert( fetchedItemsStartIndex != null && !fetchedItemsStartIndex.IsEstimate, "This case is supposed to be handled by ReplaceCache" );

        List<T> data = result.FetchedItems.ToList();
        int insertionIndex = Convert.ToInt32( fetchedItemsStartIndex.Value );

        //Set the data to be merge in the appropriate orientation.
        if( !result.IsFetchingForward() )
        {
          insertionIndex -= ( result.FetchedItems.Count - 1 );
          data.Reverse();
        }

        this.MergeItems( insertionIndex, data );
      }
    }

    protected void ExtractIndexes(
      JumpMoveAndFetchResult<T> result,
      out EstimateInt64 fetchedItemStartIndex,
      out RelativeOffset firstItemOffset )
    {
      fetchedItemStartIndex = null;
      firstItemOffset = null;


      if( m_cachedItems.Count == 0 )
        return;

      bool haveFetchItems = ( result.FetchedItems != null && result.FetchedItems.Count > 0 );
      Nullable<int> referenceIndex = null;
      EstimateInt64 operationOffset = null;


      if( haveFetchItems )
      {
        //Try to identify using first item
        int firstIndex = m_cachedItems.IndexOf( result.FetchedItems.First() );

        if( firstIndex >= 0 )
        {
          referenceIndex = firstIndex;
          operationOffset = result.GetFetchDisplacement();
          fetchedItemStartIndex = firstIndex;
        }
      }

      if( !referenceIndex.HasValue && haveFetchItems && result.FetchedItems.Count > 1 )
      {
        int lastIndex = m_cachedItems.IndexOf( result.FetchedItems.Last() );

        if( lastIndex >= 0 )
        {
          referenceIndex = lastIndex;
          operationOffset = ( !result.Result ) ? result.GetFetchUnit() : 0;
          fetchedItemStartIndex = -( ( result.FetchedItems.Count - 1 ) * result.GetFetchUnit() ) + lastIndex;
        }
      }

      if( !referenceIndex.HasValue )
      {
        //Try to get a reference with the EndPosition
        if( result.EndPositionObject is ItemPosition )
        {
          // Fallback direction is used if the end position is place "between" two cache items.
          // This mean that the cache is "out of sync" with the source.
          int fallbackDirection =
            ( result.ExpectedFetchCount != 0 )
            ? -result.GetFetchUnit()
            : -result.GetMoveUnit();

          referenceIndex = this.FindSourcePositionIndex( result.EndPositionObject, 0, fallbackDirection );

          if( referenceIndex.HasValue )
          {
            operationOffset = 0;
            if( haveFetchItems && fetchedItemStartIndex != null )
            {
              Debug.Assert( fetchedItemStartIndex.Value == ( referenceIndex - result.GetFetchDisplacement() ) );
              fetchedItemStartIndex = referenceIndex - result.GetFetchDisplacement();
            }
          }
        }
      }

      if( !referenceIndex.HasValue && ( result.ActualMoveCount.HasValue || Math.Abs( result.ExpectedMoveCount ) == 1 ) )
      {
        referenceIndex = this.FindSourcePositionIndex(
          result.SourcePosition,
          result.ExpectedMoveCount,
          result.ExpectedFetchCount );

        if( referenceIndex.HasValue )
        {
          Nullable<long> actualMove = result.ActualMoveCount;

          if( actualMove == null && Math.Abs( result.ExpectedMoveCount ) == 1 )
          {
            actualMove = result.ExpectedMoveCount;
          }

          if( actualMove != null )
          {
            bool isApproxMove = result.ExpectedMoveCount != 0 && result.ApproximateMove;
            operationOffset = new EstimateInt64( ( actualMove.Value + result.GetFetchDisplacement() ), isApproxMove );

            if( !isApproxMove && result.FetchedItems != null )
            {
              fetchedItemStartIndex = referenceIndex + result.ActualMoveCount.Value;
            }
          }
        }
      }


      if( referenceIndex.HasValue && operationOffset != null && result.EndPositionOffset != null )
      {
        long correction = ( referenceIndex.Value + operationOffset.Value );
        bool isEstimate = operationOffset.IsEstimate | result.EndPositionOffset.IsEstimate;

        if( result.EndPositionOffset.ReferencePosition == ReferencePoint.BeforeFirst )
        {
          correction = -correction;
        }

        firstItemOffset = new RelativeOffset(
            new EstimateInt64( result.EndPositionOffset.Value + correction, isEstimate ),
            result.EndPositionOffset.ReferencePosition );
      }
    }

    private void ReplaceCache( JumpMoveAndFetchResult<T> result )
    {
      bool haveFetchItems = ( result.FetchedItems != null && result.FetchedItems.Count > 0 );

      m_cachedItems.Clear();

      this.ClearItemCountEstimates();

      if( result.TotalCount != null )
      {
        m_totalItemCount = result.TotalCount;
      }

      if( !haveFetchItems )
      {
        return;
      }

      if( result.IsFetchingForward() )
      {
        m_cachedItems.AddRange( result.FetchedItems );

        m_firstItemOffset = DataUtils.CalculateRelativeOffset(
          result.EndPositionOffset,
          -result.GetFetchDisplacement() );
      }
      else
      {
        m_cachedItems.AddRange( result.FetchedItems.Reverse() );

        m_firstItemOffset = result.EndPositionOffset;

        if( !result.Result )
        {
          this.AdjustFirstItemOffset( 1 );
        }
      }
    }

    private void MergeItems( int startInsertionIndex, List<T> data )
    {
      if( data == null )
        throw new ArgumentNullException( "data" );

      if( data.Count == 0 )
        return;

      int endInsertionIndex = startInsertionIndex + data.Count;
      int initialCacheStartIndex = 0;
      int initialCacheEndIndex = m_cachedItems.Count;
      int finalCacheStartIndex;
      int finalCacheEndIndex;



      if( endInsertionIndex <= -1 || startInsertionIndex > m_cachedItems.Count )
      {
        m_cachedItems.Clear();
        m_cachedItems.AddRange( data );

        finalCacheStartIndex = startInsertionIndex;
        finalCacheEndIndex = endInsertionIndex;
      }
      else
      {
        finalCacheStartIndex = Math.Min( startInsertionIndex, 0 );
        finalCacheEndIndex = Math.Max( endInsertionIndex, m_cachedItems.Count );

        //Replace overlap...
        int maxStartIndex = Math.Max( startInsertionIndex, 0 );
        int minEndIndex = Math.Min( endInsertionIndex, m_cachedItems.Count );

        for( int i = maxStartIndex; i < minEndIndex; i++ )
        {
          m_cachedItems[ i ] = data[ i - startInsertionIndex ];
        }

        // Append some items at the end of the cache.
        // This operation must be done before the insertion at the begin
        // of the cache.
        if( endInsertionIndex > m_cachedItems.Count )
        {
          int rangeStartIndex = m_cachedItems.Count - startInsertionIndex;
          int rangeLength = endInsertionIndex - m_cachedItems.Count;

          m_cachedItems.AddRange( data.GetRange( rangeStartIndex, rangeLength ) );
        }

        // Insert any remaining items at the start of the cache.
        if( startInsertionIndex < 0 )
        {
          m_cachedItems.InsertRange( 0, data.GetRange( 0, -startInsertionIndex ) );
        }
      }

      this.AdjustFirstItemOffset( finalCacheStartIndex - initialCacheStartIndex );
    }

    private void TrimCache( int topLimitIndex )
    {
      if( m_cachedItems.Count <= this.CacheSize )
        return;

      int removeCount = m_cachedItems.Count - this.CacheSize;
      int removeFromStart;
      int removeFromEnd;

      this.TrimCache(
        removeCount,
        topLimitIndex,
        out removeFromStart,
        out removeFromEnd );

      Debug.Assert(
        removeFromStart >= 0
        && removeFromEnd >= 0
        && removeFromStart + removeFromEnd == removeCount );

      int currentTime = Environment.TickCount;

      if( removeFromStart > 0 )
      {
        m_cachedItems.RemoveRange( 0, removeFromStart );

        this.AdjustFirstItemOffset( removeFromStart );
      }

      if( removeFromEnd > 0 )
      {
        m_cachedItems.RemoveRange( m_cachedItems.Count - removeFromEnd, removeFromEnd );
      }

      m_cachedItems.TrimExcess();
    }

    protected void AdjustFirstItemOffset( long referenceOffset )
    {
      m_firstItemOffset = DataUtils.CalculateRelativeOffset(
        m_firstItemOffset,
        referenceOffset );
    }

    private void ClearItemCountEstimates()
    {
      m_firstItemOffset = null;
    }

    internal void FlushCache( int startingIndex, bool towardStart )
    {
      if( startingIndex < 0 )
        throw new ArgumentOutOfRangeException( "startingIndex", "startingIndex must be greater than or equal to zero." );

      if( !towardStart )
      {
        if( m_cachedItems.Count > startingIndex )
        {
          int removeItemCount = m_cachedItems.Count - startingIndex;

          m_cachedItems.RemoveRange( startingIndex, removeItemCount );

          if( startingIndex == 0 )
          {
            this.ClearItemCountEstimates();
          }
        }
      }
      else
      {
        int removeItemCount = Math.Min( m_cachedItems.Count, startingIndex + 1 );

        m_cachedItems.RemoveRange( 0, removeItemCount );

        if( m_cachedItems.Count == 0 )
        {
          this.ClearItemCountEstimates();
        }
        else
        {
          this.AdjustFirstItemOffset( removeItemCount );
        }
      }
    }

    internal void FlushCache()
    {
      this.FlushCache( 0, false );
    }


    #region Private Fields

    private List<T> m_cachedItems = new List<T>( 50 );
    private Dictionary<StatParameters, StatResults> m_cachedStatResults = new Dictionary<StatParameters, StatResults>();
    private int m_cacheSize;
    private IDataHelper m_dataHelper; //null
    private bool m_disposed; //false
    private RelativeOffset m_firstItemOffset = null;

    #endregion Private Fields

    #region Private CacheJumpAsyncResult Nested Type

    private class CacheJumpAsyncResult : JumpMoveAndFetchAsyncResult
    {
      internal CacheJumpAsyncResult(
        Guid callId,
        AsyncCallback userCallback,
        object asyncState,
        JumpMoveAndFetchParameters parameters )
        : base(
          callId,
          userCallback,
          asyncState,
          parameters )
      {
      }

      internal IList<T> CacheData
      {
        get;
        set;
      }
      internal long CacheMove
      {
        get;
        set;
      }
      internal RelativeOffset CacheEndPositionOffset
      {
        get;
        set;
      }
      internal EstimateInt64 CacheTotalCount
      {
        get;
        set;
      }
    }

    #endregion Private CacheJumpAsyncResult Nested Type

    #region Private CachePositionState Enum Nested Type

    private enum CachePositionState
    {
      Maybe,
      Yes,
      No
    };

    #endregion Private CachePositionState Enum Nested Type
  }
}
